数据结构 Tree 二叉树的层序遍历
二叉树的宽度优先遍历
二叉树的宽度优先遍历
public static void treeWidth(TreeNode head) {
if (head == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(head);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
System.out.print(cur.value + " ");
if (cur.left != null) queue.add(cur.left);
if (cur.right != null) queue.add(cur.right);
}
}
output
| |-------60
|-------32
| |-------75
32
| | |-------97
| |-------46
| | |-------2
|-------22
| | |-------8
| |-------94
| | |-------42
32 22 32 94 46 75 60 42 8 2 97
注：打印二叉树的工具可以在前中后序遍历那篇博客找到
什么是层序遍历 🔥
上面的宽度优先遍历是逐层的打印 Tree，但是它并不知道当前节点位于哪一层，如果想要知道位于哪一层需要使用层序遍历。层序遍历就是逐层遍历树结构。
补充知识：广度优先搜索是一种广泛运用在树或图这类数据结构中，遍历或搜索的算法。 该算法从一个根节点开始，首先访问节点本身。 然后遍历它的相邻节点，其次遍历它的二级邻节点、三级邻节点，以此类推。
当我们在树中进行广度优先搜索时，我们访问的节点的顺序是按照层序遍历顺序的。
下面用两题来介绍层序遍历如何使用（核心都是队列），重点掌握第二道题，第一题的方法其实空间复杂度有点高
找到层最大的宽度
这个参考 左神的视频 1:51:00
这里虽然看起来很复杂，其实很简单，就是通过一个 Map 来保存当前节点所在层数，然后每次在子节点入队的时候 Map 保存的这个子节点的层数加一
/**
* 返回层最大的宽度
*/
public static int treeMaxWidth(TreeNode head) {
if (head == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(head);
HashMap<TreeNode, Integer> levelMap = new HashMap<>();
levelMap.put(head, 1);// 初始层为 1
int curLevel = 1; // 当前所在层
int curLevelNodeCount = 1; // 当前层节点计数
int max = Integer.MIN_VALUE;
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
int curNodeLevel = levelMap.get(cur); // 取得当前节点所在层数
if (curNodeLevel == curLevel) { // 如果当前节点属于 curLevel 记录的层
curLevelNodeCount++; // 当前层 Node 数量加一
} else {
curLevel++;
curLevelNodeCount = 1; // 初始化计数器（因为已经入队一个数了，所以这里初始化为一）
}
if (cur.left != null) {
levelMap.put(cur.left, curNodeLevel + 1); // 它的子节点层数加一
queue.add(cur.left);
}
if (cur.right != null) {
levelMap.put(cur.right, curNodeLevel + 1); // 它的子节点层数加一
queue.add(cur.right);
}
max = Math.max(max, curLevelNodeCount); // 当前层结束时比对最大值
}
return max;
}
output
| |-------7
|-------90
| | |-------55
| |-------18
| | |-------88
74
| | |-------96
| |-------3
| | |-------61
|-------83
| | |-------49
| |-------89
| | |-------61
6
取得每一层的节点 ⭐
这题比较特殊，需要返回的是 List<List<Integer>> 所以需要对上面代码稍加改变
示例：
二叉树：[3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回其层序遍历结果：
[
[3],
[9,20],
[15,7]
]
这种方法也挺简单，就是通过一个 for 循环之前先提前记录一层里面有多少个节点，然后再把这一层的全部节点入队，所以每次大 while 循环结束后，表示当前层的节点已经全部入队了。
public static void main(String[] args) {
TreeNode root = new TreeNode(1,
new TreeNode(2,new TreeNode(4),new TreeNode(5)), new TreeNode(3));
System.out.println(levelOrder(root));
}
public static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if (root == null) return res;
queue.add(root);
while (!queue.isEmpty()) {
// 注意这个要保存下来，否则会因为 remove 或 add 而变动
int length = queue.size();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < length; i++) {
TreeNode temp = queue.remove();
list.add(temp.val);
if (temp.left != null) {
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
}
res.add(list);
}
return res;
}
队列最多装两个 Node，因为每一次 for 循环都只是取得队列第一个 Node 的左右节点
改进：找到层最大的宽度
使用上面这种方法改进 找到层最大的宽度 这题，使用无需依赖 HashMap
/**
* 返回层最大的宽度
*/
public static int treeMaxWidth(TreeNode head) {
if (head == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(head);
int max = Integer.MIN_VALUE;
while (!queue.isEmpty()) {
int length = queue.size();
int count = 0;
for (int i = 0; i < length; i++) {
TreeNode cur = queue.poll();
count++;
if (cur == null) break;
if (cur.left != null) queue.add(cur.left);
if (cur.right != null) queue.add(cur.right);
}
max = Math.max(max, count); // 当前层结束时比对最大值
}
return max;
}
补充：层序遍历
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> result = new ArrayList<>();
if (root == null) return result;
// LinkedList 继承自队列接口
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()) {
TreeNode temp = queue.pop();
if (temp.left != null) {
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
result.add(temp.val);
}
return result;
}
}
返回值：
[5,4,3,2,1]
二叉树井号法创建树 ⛔
了解就好
动态创建树有一种方法是根据先序和中序遍历的结果推导出树的结构中内存中创建，如下面介绍的几节那样，还有一种就是使用 # 号
有以下这么一组数据：
1 2 4 # # # 3 # #
数据中的 # 号代表了一棵树的结尾，也就是说，# 号前面一个的数据可能是一个叶子节点，也可能是一个没有左子节点的节点。这取决于这个数据后面跟随了几个 # 号。
# 号法推导一棵树是使用先序遍历（根、左、右）的方式推导的。
那么上面这组数据，我们依次来看，具体的排列是什么样子呢？
1一定是整棵树的根节点，因为线序遍历优先记录的就是根节点2一定是1的左子节点4就有异议了，他可能是1的右子节点，也有可能是2的左子节点或2的右子节点。但是我们要想到，如果是1的右子节点，那么证明2肯定已经是左侧子树的叶子节点了，2的后面应该跟着两个#号代表左侧节点的结束标记，而明显上面给出的数据不是这样的，所以4为1的右子节点不成立，并且间接的证明了，4一定是2的左子树，因为2后面没有#号，而紧随其后的是4，所以可以确定，4是2的左子节点。
# 代表一个节点的结束，紧随 4 的后面，证明是 4 的左侧节点。
# 有跟着一个结束标记，紧随上一个 # ，证明这是 4 的右侧节点。
【已经组建起来的结构】
# 在连续两个结束标记后，又紧随其后的跟着一个 #，看上图，既然 4 已经是叶子节点，那么证明 2 的左侧子树已经遍历完毕，接下来应该是 2 的右子树了。所以这个 # 号是 2 的右子树结束标记。
链接后的树结构如下图：
上图中，1 的左侧子树已经全部填充完毕了，那么接下来这个 3 一定就是 1 的右子树。
# # 最后两个都是井号，毋庸置疑，肯定代表节点 3 已经是叶子节点了。最后组成的图如下：
填充每个节点的下一个右侧节点指针
给定一个 完美二叉树（满二叉树，如上图所示），其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。
就是使用上面的层序遍历
public Node connect(Node root) {
if (root == null)
return null;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()) {
int length = queue.size();
for (int i = 0; i < length; i++) {
Node node = queue.poll();
// 注意：这里要用 peek 取出元素但不删除，因为这里只是传递指针
if(i < length -1) node.next = queue.peek();
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
}
// 因为上面都是操作指针，所以直接返回 root
return root;
}